1. Field of the Invention
The present invention relates to an apparatus and method of signal processing, and more specifically to a lookup table (LUT) circuit capable of approximating a variety of functions by receiving an N-bit digital input signal and providing an M-bit digital output signal by utilizing interpolation to significantly increase the precision of the output signal provided by the LUT without requiring an increase in the number of LUT entries.
2. Description of the Related Art
LUTs, implemented in either hardware or software, are used in many computer related fields such as computer graphics, image processing and analog or digital video processing, to convert one function into another function. A LUT is an example of a trade-off between memory usage and the amount of computation. One of the more common applications of LUTs is in computer graphics and image processing. In order to provide an image of an object on a display device (e.g., such as a cathode ray tube (CRT) of a display terminal), an image of an object is typically recorded by a camera (video or the like) by transforming a representation of the object into an electronic signal in analog or digital form. Then, when desired, the electronic signal is provided to the display terminal for display of the image.
Typically, display devices such as CRTs process electronic signals and output (i.e., display) light corresponding to representations of these signals (e.g. luminance) in a non-linear manner. U.S. Pat. No. 5,196,924 (the entire disclosure of which is incorporated herein by reference) provides a useful explanation of this phenomenon at Cols. 1-3. For this reason, in order to display the image of the object as it is intended to be viewed (i.e., to compensate for the non-linear behavior of the CRT), either the camera or the circuitry associated with the display terminal must modify (i.e., apply a transfer function to) the electronic signal before light corresponding to the electronic signal is output by the CRT. This signal compensation (i.e., application of a transfer function) is commonly called "gamma correction", as explained in U.S. Pat. No. 5,196,924.
A typical computer graphics display includes at least three LUTs each having 2.sup.Q entries, wherein each LUT entry contains M-bits (see FIG. 1). For example, a typical LUT maps a Q (e.g., a 6 or more) bit input signal to an M (e.g., a 6 or more) bit output signal, allowing for an arbitrary input to output mapping function that is fully precomputed and stored in memory (i.e., LUT). The use of a LUT stored in a memory of some type, typically an electronic memory chip, is a common technique for implementing gamma correction. One example of a LUT embodied in a chip is Part No. Bt473 available from Brooktree Corporation, of San Diego, Calif. A more detailed discussion of the interaction of display terminals, "gamma correction" and LUTs is provided in Computer Graphics by Foley & Van Dam (1990), at pages 166-170, 564-567 and 860-861, which pages are incorporated herein by reference.
LUTs have the inherent characteristic that the number of LUT entries increases exponentially as the number of bits of the input signal that are utilized to select the LUT entry increases. In general, a LUT of 2.sup.Q entries will be required for a Q-bit input signal. For example, an 8-bit input signal requires a LUT with 2.sup.8 =256 entries, while a 12-bit input signal requires 2.sup.12 =4096 entries. As the number of bits in the input signal becomes larger, at some point, depending on the current level of technology, the LUT memory size becomes prohibitively large and expensive, while the processing speed decreases.
Referring now to FIG. 1, in order to maintain processing speed and reduce the number of LUT entries (e.g., to &lt;2.sup.N entries where N is the number of bits of the input signal), it is generally accepted to use less than the total number of bits (e.g., Q bits) of the N-bit input signal to select the appropriate LUT entry. This conventional use of only a portion of the input signal to determine the appropriate LUT entry is shown in FIG. 1. More specifically, FIG. 1 shows mapping of Q bits of an N-bit input signal (Q.ltoreq.N) to an M-bit LUT output signal.
A drawback to limiting the number of input signal bits that are utilized to select the LUT entry is that a substantial amount of information (e.g., the N minus Q unused bits of the N-bit input signal) relating to the object image is not employed in determining the proper LUT entry and, correspondingly, the output signal/image. Thus, the signal output by the LUT includes a certain amount of error (for example, rounding or truncation error) due to inaccuracies introduced by the non-use of information present in the input signal. This leads to a loss of precision of the signal output by the LUT, which may be significant in certain applications. Since the storage, transfer and manipulation of graphic and video images typically involves the application of LUTs at several stages of processing, the introduction of even a relatively minor amount of error by each LUT can accumulate until the total error introduced becomes significant and objectionable.
One known technique for reducing the number of LUT entries relies on interpolation. As disclosed, for example, in U.S. Pat. No. 5,568,596, one portion of the input signal (i.e., the four most significant bits of an eight bit input signal) is used to identify two LUT entries. Then, another portion of the input signal (i.e., the four least significant bits) are used to calculate an interpolation value between the two selected LUT entries. Since in such a prior art technique more than one LUT entry is required for interpolation, a dual-port (i.e., dual input) LUT (RAM) is used that receives two LUT entry selection signals, one from each of two independent LUT entry selectors. A drawback to utilizing a dual-port RAM is that this device typically costs more than a single-port RAM. In addition, dual-port RAMs require more chip area than single-port RAMs (in some technologies, dual-port RAMs require twice the chip area as single-port RAMs). Moreover, dual-port RAMs typically operate at a slower speed than single-port RAMs.